#include<iostream>
using namespace std;
#include<vector>
#include<string>
class Solution {
public:
    string path;
    vector<string> path1;
    vector<vector<string>> ans;
    int pd() {
        int left = 0, right = path.size() - 1;
        while (left < right) {
            if (path[left++] != path[right--])
                return false;
        }
        return true;
    }
    void dfs(string& s, int now) {
        if (now == s.size()) {
            ans.push_back(path1);
            return;
        }
        for (int i = now; i < s.size(); ++i) {
            path += s[i];
            if (pd()) {
                string help = path;
                path1.push_back(path);
                path = "";
                dfs(s, i + 1);
                path = help;
                path1.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string& s) {
        dfs(s, 0);
        return ans;
    }
};